package syf.balacnce;

public class BalanceBinaryTree {
    public static void main(String[] args) {
//        int[] arr={4,3,6,5,7,8};
//        int[] arr={10,12,8,9,7,6};
        int[] arr={10,11,7,6,8,9};
//        int[] arr={2,1,6,5,7,3};
        balanceTree binaryTree=new balanceTree();
        for (int i:arr){
            binaryTree.add(new Node(i));
        }
        System.out.println("中序遍历");
        binaryTree.midShow();
        System.out.println("平衡之后树高度="+binaryTree.root.getHeight());
        System.out.println("平衡后前左子树高度="+binaryTree.root.leftHeight()+"\n平衡后前右子树树高度="+binaryTree.root.rightHeight());
        System.out.println(binaryTree.root);
    }
}
class balanceTree{
    Node root;
    public void add(Node node){
        if (root==null){
            root=node;
        }else {
            root.add(node);
        }
    }
    public void midShow(){
        if (root==null){
            System.out.println("空树");
        }else {
            root.midShowAll();
        }
    }
    //左旋转
    public void leftRotation(){
        if (root!=null){
            root.leftRotation();
        }
    }
    /**
     * @param val 要删除的结点的值
     */
    //删除结点
    public void delete(int val){
        if (root==null){
            System.out.println("空树");
        }else {
            if (root.value==val&&root.left==null&&root.right==null){
                root=null;
            }else {
                root.deleteNode(val);
            }
        }
    }
}
class Node{
    Node left;
    Node right;
    int value;

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
    public void add(Node node){
        if (node!=null){
            if (this.left==null&&this.value>=node.value){
                this.left=node;
            }
            else if (this.left!=null&&this.value>=node.value){
                this.left.add(node);
            }
            if (this.right==null&&this.value<node.value){
                this.right=node;
            }
            else if (this.right!=null&&this.value<node.value){
                this.right.add(node);
            }
        }
        //添加完成一个结点后，如果右子树的高度-左子树高度>1 发生左旋转
        if (this.rightHeight()-this.leftHeight()>1){
            if (this.right.leftHeight()>this.right.rightHeight()) {//符合左旋转条件时，如果当它的左子树的右子树的高度大于它的左子树的左子树的高度时，需先进行左旋转
                this.right.rightRotation();
            }
            leftRotation();
        }else if (this.leftHeight()-this.rightHeight()>1){//添加完成一个结点后，如果左子树的高度-右子树高度>1 发生右旋转
            if (this.left.rightHeight()>this.left.leftHeight()){//符合右旋转条件时，如果当它的左子树的右子树的高度大于它的左子树的左子树的高度时，需先进行左旋转
                this.left.leftRotation();
            }//旋转完成后再右旋转
            rightRotation();
        }
    }
    //中序遍历
    public void midShowAll(){
        if (this.left!=null){
            this.left.midShowAll();
        }
        System.out.println(this);
        if (this.right!=null){
            this.right.midShowAll();
        }
    }
    //左旋转
    public void leftRotation() {
        //先创建一个新结点，和当前结点的值一样
        Node tmp=new Node(this.value);
        //讲当前结点的左结点复制给新结点的左结点
        tmp.left=this.left;
        //把当前结点的右节点的左结点复制给新结点的右节点
        tmp.right=this.right.left;
        //把当前结点的右节点的值复制给当前结点
        this.value=this.right.value;
        //把当前结点的右节点的右节点复制给当前结点的右节点
        this.right=this.right.right;
        //把新结点挂在当前结点的左结点上
        this.left=tmp;
    }
    //右旋转
    public void rightRotation() {
        Node tmp=new Node(this.value);
        tmp.right=this.right;
        tmp.left=this.left.right;
        this.value=this.left.value;
        this.left=this.left.left;
        this.right=tmp;
    }
    //当前结点的高度
    public int getHeight(){
        return Math.max(left==null?0:left.getHeight(),right==null?0:right.getHeight())+1;
    }
    //右子树的高度
    public int rightHeight(){
        if (right!=null)
            return right.getHeight();
        else return 0;
    }
    //左子树的高度
    public int leftHeight(){
        if (left!=null)
            return left.getHeight();
        else return 0;
    }
    //删除结点
    public void deleteNode(int val){
        Node target = this.findTarget(val);
        Node targetParent = this.findTargetParent(val);
        if (target==null){//没有要删除的结点
            System.out.println("没有找到要删除的结点");
        }else {
            if (targetParent!=null){//要删除的结点不为根结点
                //要删除的为叶子结点
                if (target.left==null&&target.right==null){
                    if (targetParent.left!=null&&targetParent.left==target){//判断要删除的叶子结点是否在父结点的左边
                        targetParent.left=null;
                    }else if (targetParent.right!=null&&targetParent.right==target){//判断要删除的叶子结点是否在父结点的右边
                        targetParent.right=null;
                    }
                }else if (target.left!=null&&target.right!=null){//要删除的有两个子结点，替补规则左边找最大，或者右边找最小，选择右边找最小
                    target.value= findMinVal(target.right);
                }else{//要删除的有一个子结点
                    if (targetParent.left==target&&target.left==null){//要删除的结点为父结点的左结点，且要删除结点的左结点不为空
                        targetParent.left=target.right;
                    }else if (targetParent.left==target){//要删除的结点为父结点的左结点，且要删除结点的右结点但不为空
                        targetParent.left=target.left;
                    }else if (targetParent.right==target&&target.right!=null){//要删除的结点为父结点的右结点，且要删除结点的左结点不为空
                        targetParent.right=target.right;
                    }else if (targetParent.right==target){
                        targetParent.right=target.left;
                    }
                }
            }else {//要删除的结点为根结点
                //右节点不为空
                if (target.right!=null) {
                    target.value = findMinVal(target.right);
                }else if (target.left!=null){//左结点不为空
                    target.value = findMaxVal(target.left);
                }
            }
        }
    }
    //找到要删除的结点
    public Node findTarget(int val){
        if (this.value==val){
            return this;
        }else {
            if (this.left!=null&&this.value>=val){//当前结点的值大于要删除的结点，往左边找
                return this.left.findTarget(val);
            }else if (this.right!=null&&this.value<val){
                return this.right.findTarget(val);
            }else {
                return null;
            }
        }
    }
    //找到要删除结点的父结点
    public Node findTargetParent(int val){
        if (this.left!=null&&this.left.value==val||this.right!=null&&this.right.value==val){
            return this;
        }else {
            if (this.left!=null&&this.value>=val){//当前结点的值大于要删除的结点，往左边找
                return this.left.findTargetParent(val);
            }else if (this.right!=null&&this.value<val){
                return this.right.findTargetParent(val);
            }else {
                return null;
            }
        }
    }
    //查找以传入结点为根结点树的最小值
    public int findMinVal(Node nodes){
        Node tmp=nodes;
        while (tmp.left!=null){
            tmp=tmp.left;
        }
        deleteNode(tmp.value);
        return tmp.value;//返回找到结点的值
    }
    //查找以传入结点为根结点树的最大值
    public int findMaxVal(Node nodes){
        Node tmp=nodes;
        while (tmp.right!=null){
            tmp=tmp.right;
        }
        deleteNode(tmp.value);
        return tmp.value;//返回找到结点的值
    }
}
